package binTreeDeSe;

/**
 *  请实现两个函数，分别用来序列化和反序列化二叉树
 *
 * 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
 *
 * 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
 *
 * 例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树
 *
 *测试用的例子
 *           1
 *         /  \
 *       2     3
 *     /  \   /  \
 *    4   #  5   6
 *  /  \    /\   /\
 * #    #  # #  #  #
 *
 * 先序结果为：1,2,4,#,#,#,3,5,#,#,6,#,#
 *
 * 中序的结果：#,4,#,2,#,1,#,5,#,3,#,6,#
 * 中序有二义性，如下图所示，所以不能用中序作为序列化的顺序
 *                4
 *             /     \
 *           #       2
 *                 /  \
 *               #    1
 *                  /  \
 *                #     5
 *                    /  \
 *                  #     3
 *                      /   \
 *                     #    6
 *                         /\
 *                        # #
 * 后序过滤的结果是：#,#,4,#,2,#,#,5,#,#,6,3,1
 *
 *
 * */
public class Solution {
    private int idx = 0 ;
    private int afterIdx = 0 ;
    public void setAfterIdx(int idx){
        this.afterIdx = idx ;
    }
    public String serializeBefore(TreeNode root){
        if(null == root){
            return "#";
        }
        return root.getVar() + "," + serializeBefore(root.getLeft()) + "," + serializeBefore(root.getRight());
    }
    public String serializeMid(TreeNode root){
        if(null == root){
            return "#";
        }
        return serializeMid(root.getLeft()) + "," + root.getVar() + "," + serializeMid(root.getRight());
    }
    public String serializeAfter(TreeNode root ){
        if(null == root){
            return "#" ;
        }
        return serializeAfter(root.getLeft()) + "," +serializeAfter(root.getRight())  + "," + root.getVar();
    }
    public TreeNode deserializeAfter(String in ){
        String[] chs = in.split(",");
        if( afterIdx == 0 ){
            return null ;
        }
        if(chs[afterIdx].equals("#")){
            return null ;
        }
        TreeNode rs = new TreeNode(Integer.valueOf(chs[afterIdx]));
        afterIdx--;
        rs.setRight(deserializeAfter(in));
        afterIdx--;
        rs.setLeft(deserializeAfter(in));
        return rs ;

    }

    public TreeNode deserializeBefore(String in ){
        String[] chs = in.split(",");
        if( idx == chs.length -1 ){
            return null ;
        }
        if(chs[idx].equals("#")){
            return null ;
        }
        TreeNode rs = new TreeNode(Integer.valueOf(chs[idx]));
        idx++;
        rs.setLeft(deserializeBefore(in));
        idx++;
        rs.setRight(deserializeBefore(in));
        return rs ;

    }
    public void forTreeNode(TreeNode root){
        if(null == root){
            return;
        }
        System.out.println(root.getVar());
        forTreeNode(root.getLeft());
        forTreeNode(root.getRight());
    }
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        treeNode1.setLeft(treeNode2);
        treeNode1.setRight(treeNode3);

        treeNode2.setLeft(treeNode4);
        treeNode3.setLeft(treeNode5);
        treeNode3.setRight(treeNode6);
        Solution s = new Solution();

//        String s1 = s.serializeBefore(treeNode1);
//        System.out.println(s1);
//        TreeNode treeNode = s.deserializeBefore(s1);
//        System.out.println(s.serializeBefore(treeNode));
//        s.forTreeNode(treeNode);
//        String s1 = s.serializeMid(treeNode1);
//        System.out.println(s1);
        String s1 = s.serializeAfter(treeNode1);
        System.out.println(s1);
        s.setAfterIdx(s1.replace(",","").length() - 1);
        TreeNode treeNode = s.deserializeAfter(s1);
        System.out.println(s.serializeAfter(treeNode));
    }

}
